\begin{centering}
\bf Laboratorio de M\'etodos Num\'ericos - Primer cuatrimestre 2012 \\
\bf Trabajo Pr\'actico N\'umero 2: Mucho ruido y pocas matrices...\\
\end{centering}

\vskip 25pt
\hrule
\vskip 11pt

{\bf Introducci\'on}

Un problema t\'ipico que se encuentra al trabajar con im\'agenes digitales es la existencia de ``ruido'' en las mismas. En pocas palabras, podemos decir que el ruido ocurre cuando el valor de uno o m\'as p\'ixeles de la imagen, no se corresponden con la realidad. La mayor\'ia de las veces, esto se debe a la calidad del equipo electr\'onico utilizado para tomar las fotograf\'ias, o bien a posibles perturbaciones introducidas al momento de transmitir la informaci\'on. Un caso muy com\'un de im\'agenes con ruido son las fotograf\'ias satelitales.

%Una forma de corregir (o reducir) este fen\'omeno en las im\'agenes es mediante la aplicaci\'on de filtros, con el objetivo de suavizar las mismas para obtener resultados m\'as cercanos a la realidad. Hoy en d\'ia, existen muchas t\'ecnicas de filtrado de im\'agenes,  muchas de ellas est\'an basadas en modelos matem\'aticos que en general se resuelven mediante m\'etodos num\'ericos.

Se puede pensar el problema de filtrar una imagen con ruido como la minimizaci\'on del siguiente funcional:
\begin{equation}
 \Pi = \int_\Omega {\frac{\lambda}{2} \left| u - \tilde{u} \right|^2 + \frac{1}{2} \lVert \nabla u \rVert^2 } d\Omega,
\label{funcional}
\end{equation}
donde $u : \Omega \subset \mathbb{R}^2 \to \mathbb{R}$ describe la imagen filtrada y
$\tilde{u} : \Omega \subset \mathbb{R}^2 \to \mathbb{R}$ la imagen a filtrar (con ruido).
De esta manera, el primer t\'ermino \emph{pesa} cuanto ruido tiene $\tilde{u}$ y el segundo \emph{pesa} la suavidad de la imagen obtenida. La constante $\lambda$ controla la importancia relativa de los dos t\'erminos.

La minimizaci\'on del funcional de la ecuaci\'on~(\ref{funcional}) da lugar a la siguiente ecuaci\'on diferencial:
% \begin{equation}
%  \lambda \left( u - \tilde{u} \right) - \nabla^2 u = 0.
% \label{ecdif}
% \end{equation}
\begin{equation}
 \lambda \left( u - \tilde{u} \right) - \left( \frac{\partial^2 u}{\partial x^2} + \frac{\partial^2 u}{\partial y^2} \right) = 0.
\label{ecdif}
\end{equation}

La soluci\'on de la ecuaci\'on~(\ref{ecdif}) que representa la imagen filtrada se puede aproximar de manera discreta utilizando el m\'etodo de diferencias finitas, lo cual conduce al siguiente sistema de ecuaciones:
\begin{equation}
 \lambda u_{i,j} - \left( u_{i-1,j} + u_{i+1,j} + u_{i,j-1} + u_{i,j+1} - 4 u_{i,j} \right) = \lambda \tilde{u_{i,j}}
 \label{eqlin}
\end{equation}
donde ahora $u,\tilde{u} : \Omega \subset \mathbb{Z}^2 \to [0 \dots 255]$ son la versiones discretas de la imagen filtrada y la imagen original, respectivamente. Viendo la imagen $u$ como una matriz, $i,j$ son los \'indices de fila y columna de cada elemento (p\'ixel)  de la matriz, donde el 0 es representado por el color negro y el 255 por el blanco\footnote{Este modelo de filtrado de im\'agenes se puede extender a im\'agenes color RGB, repitiendo el proceso descripto para cada componente de color.}.

{\bf Enunciado}

El objetivo principal de este trabajo pr\'actico es implementar un programa para eliminar (o reducir) el ruido en im\'agenes digitales. Para ello, el programa deber\'a tomar como entrada una imagen (supuestamente con ruido) y resolver la ecuaci\'on~(\ref{ecdif}) por el m\'etodo de diferencias finitas (resolviendo el sistema de ecuaciones dado por las ecuaciones~(\ref{eqlin})). Finalmente, el programa deber\'a devolver la versi\'on filtrada de la im\'agen. La constante $\lambda$ involucrada en las ecuaciones debe ser un par\'ametro del programa de manera tal que se pueda luego experimentar con ella.

Adicionalmente, el programa implementado deber\'a ser capaz de procesar im\'agenes de gran tama\~no. Para ello, se pide implementar una funcionalidad extra que permita reducir las im\'agenes antes de ser procesadas y que, luego del proceso, revierta esta reducci\'on para lograr as\'i una imagen de las dimensiones originales. El {\em factor de reducci\'on} a utilizar debe ser un par\'ametro del programa. Por ejemplo, si se desea procesar una imagen de 5 {\em megap\'ixeles}\footnote{Un megap\'ixel equivale a un mill\'on de p\'ixeles.}, puede ocurrir que el tiempo de proceso necesario exceda lo que uno est\'a dispuesto a esperar, con lo cual ser\'ia posible reducir la imagen con un cierto factor de reducci\'on y aplicar el proceso de filtrado a una imagen de menores dimensiones. Obviamente, la salida del programa deber\'a invertir este proceso para retornar una imagen de dimensiones id\'enticas a la imagen original. Estos procesos llevan el nombre de {\em submuestreo} (la reducci\'on) y {\em sobremuestreo} (la ampliaci\'on) y existen muchas formas de realizarlos. La manera de realizarlos para este trabajo queda a criterio del grupo.

% El proceso de filtrado descripto puede aplicarse tambi\'en en forma iterativa. Es decir, luego de la primer pasada de filtrado, es posible repetir el procedimiento sobre la imagen obtenida con el objetivo de seguir reduciendo el ruido en la misma. El programa implementado deber\'a permitir realizar este proceso iterativo y la cantidad de iteraciones deber\'a ser un par\'ametro del programa, sobre el cual sea posible experimentar.

Tanto el valor de la constante $\lambda$ como el factor de reducci\'on
%  y la cantidad de iteraciones de filtrado 
tendr\'an un fuerte impacto en la calidad de las im\'agenes obtenidas. 
% Los dos \'ultimos impactar\'an 
El factor de reducci\'on impactar\'a
tambi\'en en los tiempos de ejecuci\'on. Para medir estos impactos, se deber\'a realizar una experimentaci\'on computacional cuyos resultados deber\'an ser plasmados en el informe del trabajo.

{\bf Experimentaci\'on}

Una forma de medir la calidad visual de las im\'agenes filtradas, es a trav\'es del PSNR ({\em Peak Signal-to-Noise Ratio}).
EL PSNR es una m\'etrica ``perceptual'' (acorde a lo que perciben los humanos) y nos da una forma de medir la calidad de una imagen perturbada, siempre y cuando se cuente con la imagen original. 
Cuanto mayor es el PSNR mayor es la calidad de la imagen. La unidad de medida es el decibel (db) y se considera que una diferencia de 0.5 db ya es notada por la vista humana. El PSNR se define como:
$$
\mathit{PSNR} = 10 \cdot \log_{10} \left( \frac{\mathit{MAX}^2_u}{\mathit{ECM}} \right)
$$
donde $MAX_u$ define el rango m\'aximo de la imagen (para nuestro caso ser\'ia 255) y ECM es el {\em error cuadr\'atico medio}, definido como:
$$
\frac{1}{N} \sum_{i,j}{(u^0_{i,j} - u_{i,j})^2} 
$$
donde $N$ es la cantidad de p\'ixeles de la imagen, $u^0$ es la imagen original y $u$ es la imagen perturbada (o en nuestro caso, la imagen recuperada).

La experimentaci\'on propuesta para el presente trabajo pr\'actico consiste en analizar la calidad de las im\'agenes reconstru\'idas y los tiempos de ejecuci\'on en funci\'on de: \\[-8mm]
	\begin{itemize}
		\item el nivel de ruido en la imagen, \\[-6mm]
		\item la constante $\lambda$ y\\[-6mm]
		\item el factor de reducci\'on. \\[-6mm]
% 		\item la cantidad de iteraciones de filtrado. \\[-8mm]
	\end{itemize}	
	
Dado que para medir la calidad se requiere contar con la imagen original, se deber\'an utilizar im\'agenes \emph{ruidosas} generadas artificialmente (por ejemplo, sumando o restando a los p\'ixeles de la imagen original valores generados aleatoriamente con distribuci\'on uniforme).
	
{\bf Formatos de archivos de entrada}

Para leer y escribir im\'agenes sugerimos utilizar el formato {\em raw} binario \texttt{.pgm}\footnote{\url{http://netpbm.sourceforge.net/doc/pgm.html}}. 
El mismo es muy sencillo de implementar y compatible con muchos gestores de fotos\footnote{XnView \url{http://www.xnview.com/}} y Matlab.


\vskip 20pt
\hrule
\vskip 15pt

% {\bf Entregas parciales}
% \vspace{-15pt}
% \begin{description}
%   \setlength{\itemsep}{0pt}
%   \setlength{\parskip}{0pt}
%   \setlength{\parsep}{0pt}
%  \item[1 de abril:] An\'alisis te\'orico del error de los m\'etodos. Implementaci\'on b\'asica usando \texttt{float} y \texttt{double}.
%  \item[8 de abril:] Implementaci\'on de los m\'etodos en aritm\'etica finita de $t$ d\'igitos. Resultados preliminares.
% \end{description}

% \vskip 15pt
% \hrule
% \vskip 11pt

{\bf Fechas de entrega}
\vspace{-15pt}
\begin{itemize}
	\item Formato Electr\'onico: {\bf martes} 22 de mayo de 2012, hasta las 23:59 hs, a \texttt{metnum.lab@gmail.com}\\[-6mm]
	\item Formato f\'isico: {\bf mi\'ercoles} 23 de mayo de 2012, de 17 a 19 hs.
\end{itemize}
%\vspace{-15pt}
%\begin{description}
%  \setlength{\itemsep}{1pt}
%  \setlength{\parskip}{1pt}
%  \setlength{\parsep}{1pt}
% \item[Formato Electr\'onico:] {\bf martes} 22 de mayo de 2012, hasta las 23:59 hs, a la direcci\'on: 
%
%  {\emph{metnum.lab@gmail.com}}
%%  \item[Formato f\'isico y experimentaci\'on en clase:] 13 de abril de 2012, de 17 a 21 hs.
% \item[Formato f\'isico:] {\bf mi\'ercoles} 23 de mayo de 2012, de 17 a 19 hs.
%\end{description}


